public class question_21 {
}


//21. 合并两个有序链表
//注意这道题要求的是合并而不能另外再生成一个链表把结果返回
class Solution_21 {
    public ListNode createLinkedList(int[] nums) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        for (int num : nums) {
            curr.next = new ListNode(num);
            curr = curr.next;
        }
        return dummy.next;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//  第一步，先考虑一些特殊值的情况
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
//        定义返回的头指针,
        ListNode result=list1.val<=list2.val?list1:list2;
        while (list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                while (list1.next!=null&&list1.next.val<=list2.val){
                    list1=list1.next;
                }
//                这里的temp和temp前面的节点是比当前list2节点的值要小的，所以要设置temp.next=list2
                ListNode temp=list1;
                list1=list1.next;
                temp.next=list2;
            }else {
//                同样的道理，只不过反了过来
                while (list2.next!=null&&list2.next.val<list1.val){
                    list2=list2.next;
                }
//                这里的temp和temp前面的节点是比当前list2节点的值要小的，所以要设置temp.next=list2
                ListNode temp=list2;
                list2=list2.next;
                temp.next=list1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution_21 solution_21 = new Solution_21();
        int[] nums1 = {1, 2, 4, 5, 7, 9, 20, 25};
        ListNode list1 = solution_21.createLinkedList(nums1);

        int[] nums2 = {3, 3, 5, 8, 9, 11, 12};
        ListNode list2 = solution_21.createLinkedList(nums2);
        System.out.println(solution_21.mergeTwoLists(list1, list2));

    }
}
